package com.mamingchao.basic.arraysort.dutch_national_flag;

/**
 * 荷兰国旗的问题
 * 因为荷兰国旗 是红白蓝 三种颜色
 *
 * 给定一个整数数组，给定一个值K，这个值在原数组中一定存在，要求把数组中小于K的元素放到数组的左边，
 * 大于K的元素放到数组的右边，等于K的元素放到数组的中间，最终返回一个整数数组，其中只有两个值，
 * 分别是等于K的数组部分的左右两个下标值。
 * Created by mamingchao on 2021/3/16.
 */
public class DutchNationalFlag {

    public static void main(String[] args) {
        int[] arr = {1,4,6,9,7,2,3,5,8,10};
        String index = sort(arr,6);
        System.out.println(index);
        printArr(arr);
    }
    /**
     * value 值一定在 数组中
     * 定义 int low 为  小于value 值 最右边元素的索引值
     * 定义 int high 为  小于value 值 最右边元素的索引值
     * 定义 int current 为  遍历数组，遍历到 当前元素的索引值
     *
     * 如果 arr[current] < value  交换 arr[current] low 索引所指的下一个元素,current++,less ++
     * 如果 arr[current] > value  交换 arr[current] high 索引所指的前一个元素 high --
     * 如果 arr[current] == value, current++
     * 当 current >= high的时候，停止遍历
     *
     * @param arr 原始数组
     * @param value 原始数组中的一个值
     * @return 返回 小于value 值 最右边元素的索引值 和 大于value值的最左边元素的索引值，
     * 两个整形 转成String ，用 @ 拼接
     */
    public static String sort(int[] arr,int value){

        int low = -1;
        int high = arr.length;
        int current= 0;

        while (current < high) {
            if (arr[current] < value) {
                swap(arr,++low,current++);
            } else if (arr[current] > value) {
                swap(arr, --high,current);
            } else { // arr[current] == value的情况
                current ++;
            }
        }

        return low + "@" + high;
    }


    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    private static void printArr(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + "\t");
        }
    }
}
